package leetcode_1000;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class ArrayOfDoubledPairs_954 {
	public static void main(String[] args) {
		ArrayOfDoubledPairs_954 test = new ArrayOfDoubledPairs_954();
		int []arr = new int[] {6,-4,8,4,0,8,4,0,4,8,0,4,-8,0,3,2,3,6};
		//System.out.println(test.canReorderDoubled(arr));
	}
	
	public boolean canReorderDoubled(int[] A) {
		TreeMap<Integer,Integer> pos = new TreeMap<Integer,Integer>();
		TreeMap<Integer,Integer> nil = new TreeMap<Integer,Integer>((o1,o2)->o2-o1);
		int zero = 0;
		for(int i:A) {
			if(i == 0) {
				++zero;
				continue;
			}
			if(i > 0) {
				int count = pos.getOrDefault(i, 0)+1;
				pos.put(i, count);
			}else {
				int count = nil.getOrDefault(i, 0)+1;
				nil.put(i, count);
			}
		}
		if(zero%2 == 1||pos.size()%2 == 1||nil.size()%2 == 1) return false;
		while(!pos.isEmpty()) {
			Map.Entry<Integer,Integer> small = pos.pollFirstEntry();
			Integer now = pos.get(small.getKey()*2);
			if(now == null||now != small.getValue()) return false;
			pos.remove(small.getKey()*2);
		}
		while(!nil.isEmpty()) {
			Map.Entry<Integer,Integer> small = nil.pollFirstEntry();
			Integer now = nil.get(small.getKey()*2);
			if(now == null||now != small.getValue()) return false;
			nil.remove(small.getKey()*2);
		}
		return true;
	}
	
	//题目看错了 以为是随意组成pairs
	public boolean canReorderDoubled2(int[] A) {
		TreeMap<Integer,Integer> pos = new TreeMap<Integer,Integer>();
		TreeMap<Integer,Integer> nil = new TreeMap<Integer,Integer>((o1,o2)->o2-o1);
		int zero = 0;
		for(int i:A) {
			if(i>0) {
				int count = pos.getOrDefault(i, 0)+1;
				pos.put(i, count);
			}else if(i<0){
				int count = nil.getOrDefault(i, 0)+1;
				nil.put(i, count);
			}else {
				++zero;
			}
		}
		if(zero%2 == 1) return false;
		while(!pos.isEmpty()) {
			Map.Entry<Integer,Integer> pre = pos.pollFirstEntry();
			Integer now = pos.get(pre.getKey()*2);
			if(now == null) return false;
			if(now<pre.getValue()) return false;
			if(now == pre.getValue()) pos.remove(pre.getKey()*2);
			else pos.put(pre.getKey()*2, now-pre.getValue());
		}
		while(!nil.isEmpty()) {
			Map.Entry<Integer,Integer> pre = nil.pollFirstEntry();
			Integer now = nil.get(pre.getKey()*2);
			if(now == null) return false;
			if(now<pre.getValue()) return false;
			if(now == pre.getValue()) nil.remove(pre.getKey()*2);
			else nil.put(pre.getKey()*2, now-pre.getValue());
		}
		return true;
	}
	
	public boolean canReorderDoubled1(int[] A) {
        PriorityQueue<Integer> pos = new PriorityQueue<Integer>();
        PriorityQueue<Integer> nil = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1-o1;
			}
        	
        });
        for(int i:A) {
        	if(i>=0) {
        		pos.add(i);
        	}else {
        		nil.add(i);
        	}
        }
        if(pos.size()%2 == 1) return false;
        while(!pos.isEmpty()) {
        	int i1 = pos.poll();
        	int i2 = pos.poll();
        	if(i2 != i1*2) return false;
        }
        while(!nil.isEmpty()) {
        	int i1 = nil.poll();
        	int i2 = nil.poll();
        	if(i2 != i1*2) return false;
        }
        return true;
    }
}
